package com.dyz.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class MergeKLists23 {
    public ListNode mergeKLists(ListNode[] lists) {
        //构建最小对堆
        Queue<ListNode> q = new PriorityQueue<>(new Comparator<ListNode>(){
            @Override
            public int compare(ListNode o1, ListNode o2){
                return o1.val-o2.val;
            }
        });

        for(ListNode head:lists){
            while (head!=null){
                q.offer(head);
                head = head.next;
            }
        }

        //构建节点
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (q.size()>0){
            head.next = q.poll();
            head = head.next;
            if(q.size()==0){
                head.next = null;
            }
        }
        return dummy.next;
    }
}
